package week_06;

public class Rob_2_213 {

    public int rob(int[] nums) {
        int n = nums.length;
        if(n<2) return nums[0];
        // 环形问题 迭代两次dp寻找答案
        int[][] dp0 = new int[n + 1][2];
        int[][] dp1 = new int[n + 1][2];

        // case1:第一次不偷
        dp0[1][0] = 0;
        dp0[1][1] = Integer.MIN_VALUE;

        // case2:第二次偷第一个
        dp1[1][0] = 0;
        dp1[1][1] = nums[0];
        for (int i = 2; i <= n; i++) {
            for (int j = 0; j <= 1; j++) {
                if (j == 0) dp0[i][0] = Math.max(dp0[i - 1][0], dp0[i - 1][1]);
                if (j == 1) dp0[i][1] = dp0[i - 1][0] + nums[i - 1];

                if (j == 0) dp1[i][0] = Math.max(dp1[i - 1][0], dp1[i - 1][1]);
                if (j == 1) dp1[i][1] = dp1[i - 1][0] + nums[i - 1];
                System.out.println(i + ":" + j + ":" + dp0[i][j]);
            }
        }
        int ans ;
        ans = Math.max(dp0[n][0], dp0[n][1]);
        ans = Math.max(ans, dp1[n][0]);
        return ans;
    }

    public int rob2(int[] nums) {
        int n = nums.length;
        if(n<2) return nums[0];
        // 环形问题 迭代两次dp寻找答案
        int[][] dp0 = new int[n + 1][2];
        // case1:第一次不偷
        dp0[1][0] = 0;
        dp0[1][1] = Integer.MIN_VALUE;
        int[][] dp1 = new int[n + 1][2];
        for (int i = 2; i <= n; i++) {
            for (int j = 0; j <= 1; j++) {
                if (j == 0) dp0[i][0] = Math.max(dp0[i - 1][0], dp0[i - 1][1]);
                if (j == 1) dp0[i][1] = dp0[i - 1][0] + nums[i - 1];
                System.out.println(i + ":" + j + ":" + dp0[i][j]);
            }
        }
        int ans = 0;
        ans = Math.max(dp0[n][0], dp0[n][1]);
        // case2:第二次偷第一个
        dp1[1][0] = 0;
        dp1[1][1] = nums[0];
        for (int i = 2; i <= n; i++) {
            for (int j = 0; j <= 1; j++) {
                if (j == 0) dp1[i][0] = Math.max(dp1[i - 1][0], dp1[i - 1][1]);
                if (j == 1) dp1[i][1] = dp1[i - 1][0] + nums[i - 1];
                System.out.println(i + ":" + j + ":" + dp1[i][j]);
            }
        }
        ans = Math.max(ans, dp1[n][0]);
        return ans;
    }
}
